DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2017.19

Comparison of Max-Plus Automata and Joint Spectral Radius of Tropical Matrices

Authors: Laure Daviaud, Pierre Guillon, and Glenn Merlet

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract

Weighted automata over the tropical semiring Zmax are closely related to finitely generated semigroups of matrices over Zmax. In this paper, we use results in automata theory to study two quantities associated with sets of matrices: the joint spectral radius and the ultimate rank. We prove that these two quantities are not computable over the tropical semiring, i.e. there is no algorithm that takes as input a finite set of matrices S and provides as output the joint spectral radius (resp. the ultimate rank) of S. On the other hand, we prove that the joint spectral radius is nevertheless approximable and we exhibit restricted cases in which the joint spectral radius and the ultimate rank are computable. To reach this aim, we study the problem of comparing functions computed by weighted automata over the tropical semiring. This problem is known to be undecidable, and we prove that it remains undecidable in some specific subclasses of automata.

Cite as

Laure Daviaud, Pierre Guillon, and Glenn Merlet. Comparison of Max-Plus Automata and Joint Spectral Radius of Tropical Matrices. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{daviaud_et_al:LIPIcs.MFCS.2017.19,
  author =	{Daviaud, Laure and Guillon, Pierre and Merlet, Glenn},
  title =	{{Comparison of Max-Plus Automata and Joint Spectral Radius of Tropical Matrices}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.19},
  URN =		{urn:nbn:de:0030-drops-81052},
  doi =		{10.4230/LIPIcs.MFCS.2017.19},
  annote =	{Keywords: max-plus automata, max-plus matrices, weighted automata, tropical semiring, joint spectral radius, ultimate rank}
}

Search Results

Documents authored by Merlet, Glenn

Comparison of Max-Plus Automata and Joint Spectral Radius of Tropical Matrices

Abstract

Cite as

Thanks for your feedback!

Could not send message